1) Field of the Invention
The present invention relates to a packet scheduler, and more particularly to a packet scheduler suitably useful in a case where a packet transfer apparatus such as a router carries out packet scheduling by using a manner of WFQ (Weighted Fair Queuing).
2) Description of the Related Art
Recently, a multimedia information communication using a network and an application for carrying out communication in a real time manner are deployed. With the deployment of the mode of utilization of the network, it is requested that the communication quality provided by the network is more firmly guaranteed and improved.
Technology of IP (Internet Protocol) and one regarding ATM (Asynchronous Transfer Mode) are technologies which support the above-introduced applications. In a router as a network relaying apparatus (packet transferring apparatus) having the technology of IP and one regarding ATM, a requested implementation of a packet scheduling is one in which packets are classified into a plurality of queues in accordance with the traffic and transferring control is effected while the requested communication quality is guaranteed.
In order to provide the communication quality requested for the network, a transmission bandwidth may be reserved for guaranteeing the bandwidth for the traffic. In this case, it is necessary for the packet transmitting apparatus to reserve a bandwidth for each traffic and transmit a packet so that the reserved bandwidth is guaranteed.
If the packet transmitting apparatus is requested as described above, the packet transmitting apparatus shall be arranged based on a packet scheduling system in which a queue block composed of a memory or the like of a FIFO (First-In First-Out) system is prepared for each traffic independently so that the bandwidth reserved for each traffic is guaranteed and output order is decided for the packets held in the queue for each traffic. As a packet scheduling system as described above, an algorithm based on WFQ (Weighted Fair Queuing) is well known. The technology of WFQ is described in a reference of, for example, A. K. Parekh and R. G. Gallager, “A Generalized Processor Sharing Approach to Flow Control in Integrated Service Networks: The Single-Node Case”, IEEE/ACM Trans. on Networking, vol.1, pp. 344–357, June 1993.
FIG. 19 is a diagram illustrative of a packet transferring technology based on a conventional WFQ algorithm implemented in a packet transferring apparatus provided on the above-described network. As shown in FIG. 19, reference numerals 101-1 to 101-n represent queue blocks, 102 a packet scheduler for deciding an output order of packets held in each of the queues 101-1 to 101-n.
In FIG. 19, packets of each traffic tr1 to trn are stored in respective queue blocks 101-1 to 101-n, and the packets stored in respective queue blocks 101-1 to 101-n are outputted in a manner of FIFO system. Also, the queue 101-i (i; 1 to n) is arranged to have a weighting coefficient φi in proportion to a reserved bandwidth. When any packet to be transmitted is stored in the queue block, the queue block is referred to as one placed in a back-log state or “active”. Now symbol φb is taken as a sum of the weighting coefficients of queue blocks in the back-log state.
According to the arrangement of the packet scheduler 102 shown in FIG. 19, in consideration of a fair assignment of a vacant bandwidth of a queue block which is placed in a non-active state, the scheduled output time of the head packet (packet to be outputted first) of each queue block (e.g., a value of Fi of the queue block 101-i) is calculated based on the following Equations (1) and (2), and a queue block holding a packet to be outputted at the highest priority is selected in accordance with the obtained scheduled output times of the head packets of respective queue blocks 101-1 to 101-n.
In this case, “ri” represents a value of a vacant bandwidth assigned to a bandwidth which is reserved for a traffic “tri” of the queue block 101-i, “ti” arrival time data indicative of a timing point when the head packet arrived at the queue block and held in the queue block 101-i, “Li” a length of the head packet, “R” a transmission speed of an output link, and “F′i” data of scheduled output time calculated when a packet is outputted last from the queue block 101-i. In order to guarantee a reserved bandwidth for all of the queues, Equation, R≧Σφi shall hold.ri=φi×R/φ  (1)Fi=max{F′i, ti}+Li/ri  (2)
That is, as shown in FIG. 20, the first term of Equation (2), or max{F′i, ti} means that a larger value (later time) is selected as a calculation reference from the scheduled output time F′i of the head packet last outputted from the queue block 101-i and the arrival time ti of a packet sequel to the head packet in the same queue block 101-i. The second term of the same equation, Li/ri represents a transfer time required when a packet with a packet length of Li is transmitted in the reserved bandwidth ri.
In other words, the first term, max{F′i, ti} means that time information serving as a calculation reference of the scheduled output time of the head packet is set to F′i or ti in accordance with the comparison between them. For example, if a packet arrives at the subject queue block 101-i soon after the last packet is outputted from this queue block, ti becomes a later time with respect to F′i. Thus, time of ti is employed as the calculation reference. Conversely, as shown in FIG. 20, if a packet arrives at the subject queue block 101-i before the packet to be outputted first is outputted from this queue block, F′i becomes a later time with respect to ti. Thus, time of F′i is employed as the calculation reference.
As described above, the packet scheduler 102 selects a queue block 101-i placed in the active state having the minimum Fi value as a packet to be outputted first, based on the comparison among Fi values calculated as described above. Then, the packet scheduler 102 provides instruction to the queue block 101-i that the head packet thereof is to be outputted.
When the scheduled output time Fi for the head packet of the selected queue block 101-i is decided, this value is utilized for calculating a value of F′i, or the scheduled output time value for a packet to be outputted next. In this way, in the packet scheduler 102, the value of Fi is subjected to an incrementing processing at every operation of packet selection. In other words, each time a single packet is selected and outputted to the network, calculation of Fi based on the new condition (using Equations (1) and (2)) is effected so as to carry out packet selection processing.
In the above-described packet transferring apparatus to which the WFQ algorithm is applied, each variable utilized in the calculation of Equations (1) and (2) is denoted by a limited number of bit length. Also, the packet arriving time counted by a timer or the like is denoted by a value of a limited number of bit length.
In the above-described conventional WFQ algorithm, however, if the above-described deviation of the scheduled output time Fi from an actual time (real time) becomes larger than a predetermined constant time, bit data indicative of the calculated value of Fi exceeds a predetermined value due to the following causes, with the result that overflow can be brought about. If overflow is brought about, the comparison of max{F′i, ti} and selection of the smallest value of Fi in the calculation of the above Equation cannot be carried out in a proper manner.
If time information is handled based on a wrap-around system, when value difference exceeds a value of the (bit length −1)th power of 2, comparison of values in terms of size cannot be carried out with accuracy.
The deviation of the scheduled output time Fi from the real time causes the following erroneous operation. That is, when the selection operation is carried out based on the WFQ algorithm to determine a queue block which has the smallest scheduled output time Fi, the value of Fi of a queue block in which overflow is brought about tends to be extremely small as compared with those of other queue blocks. Thus, the queue in which overflow is brought about is continuously selected with priority.
For this reason, other queue blocks are unreasonably restricted in assignment of a bandwidth utilized for packet transmission, with the result that it becomes impossible to guarantee the bandwidth reservation for all of the queue blocks. Further, since the comparison of the value of scheduled output time, Fi cannot be effected in a fair manner, bandwidth resources cannot be assigned to queue blocks in a fair manner. Thus, guarantee of bandwidth reservation and bandwidth assignment in a fair manner, which are originally intended in the WFQ algorithm, cannot be effected in a desired manner.
Now description will be hereinafter made on the deviation of the scheduled output time from the real time, which is the cause of overflow in the calculation step of the WFQ algorithm of Equation (2).
A first cause of deviation of the scheduled output time from the real time is a rounding-off error deriving from the restriction of bit length regarding the scheduled output time, Fi based on the WFQ algorithm. For example, a reciprocal of the reserved bandwidth ri is introduced in the second term of Equation (2). Thus, the rounding-off error deriving from the division is caused.
As described above, the value of Fi is calculated from the scheduled output time F′i of a packet which was outputted in the preceding step. Therefore, the rounding-off error deriving from the bit-length restriction can be accumulated each time a packet is outputted. Accordingly, the rounding-off error deriving from the bit error restriction of the scheduled output time calculation can cause the deviation of the scheduled output time from the real time.
As a second cause of the deviation of the scheduled output time from the real time is that there is a disagreement between an output link speed, R in accordance with the calculation based on the WFQ algorithm and an actual transmission speed of the network due to the following principal three reasons.
That is, one reason of the disagreement between an output link speed, R and the actual transmission speed of the network is that, when a value of the packet length utilized in the calculation based on the WFQ algorithm is handled, a value of a header length added in a layer lower than the IP layer or the ATM layer is sometimes not taken into account.
That is, when a packet is transferred in the network, identification information such as a header (IP header, MAC header or the like), a preamble or the like is added to the packet, and a transmission speed of the packet is determined in accordance with the transferred data size including the header information. On the other hand, when a user of the network designates a reserved bandwidth, the size of the data to be transferred is not intended to include the header data amount below a certain layer.
For this reason, the packet length in terms of a calculation of the WFQ algorithm is intended not to include the length of the header below the certain layer. In this way, there can be caused a disagreement between the data transmission speed in terms of estimation based on calculation and the real transmission speed, depending on which portion of the packet information is to be included in a target of transmission upon designating the reserved bandwidth or which portion of the real packet is to be included in an object of WFQ calculation as the packet length Li.
Also, an addition-deletion processing (transfer media converting processing, VLAN tag processing of Ethernet, a header processing to an option of IPv6) and so on are selectively effected depending on the necessity in the packet transferring apparatus. In expectation of the above header addition-deletion processing, the real transmission speed and the packet length determined by the reserved bandwidth may be estimated. However, such estimation can result in increase of processing load. In particular, a trouble can be caused when the transmission speed of the packet is intended to be increased. For this reason, it is difficult to achieve complete agreement between the bandwidth in terms of calculation and the bandwidth actually effected upon packet transmission.
A second reason of the disagreement between an output link speed, R and the actual transmission speed of the network is that, from the standpoint of management of the packet transferring apparatus, in order to ensure the assignment of reserved bandwidth, the value of R in terms of WFQ calculation is sometimes set to a value smaller than the actual transmission speed of the network.
In other words, from the WFQ management standpoint, the actual output link speed can be smaller than the value of R in terms of WFQ calculation depending on the state of congestion in the network. In such a case, if the actual output link speed becomes smaller than the value of Σ φi, the throughput of the network can be lowered due to the congestion of the network, with the result that the reserved bandwidth cannot be guaranteed for all of the queue blocks.
Thus, if it is requested to take the congestion state of the network, calculation error and so on into account, it is necessary for the value of R to be set to a safety value which can hold (R in terms of WFQ calculation)<(actual maximum transmission speed) regardless of the state of congestion of the network.
Further, a third reason of the disagreement between an output link speed, R and the actual transmission speed of the network is as follows. That is, a packet transferring algorithm different from the WFQ algorithm can be effected in an identical network in a bandwidth sharing manner. In this case, if a vacant bandwidth is provided from a bandwidth which is originally assigned to the other packet transferring algorithm, this fact means that a packet transmission is effected using a bandwidth larger than the value of R estimated by calculation when the packet is transmitted from a queue block to which the WFQ algorithm is applied. Also in this case, the output link speed R differs from the actual transmission speed of the network.
At this time, if the above second reason causes the disagreement between the output link speed R in terms of calculation based on the WFQ algorithm and the actual transmission speed of network, then the scheduled output time Fi is deviated from the real time. This deviation will be hereinafter described in more detail with an example.
It is supposed that some packets are already stored in a queue block and new packets are supplied to the queue continuously. In this case, selection is made on F′i for the first term, max{F′i, ti} of Equation (2). In this case, it is assumed that the output link speed R in terms of calculation is set to a value smaller than the value of actual transmission speed (transfer speed) of the network.
As shown in FIGS. 21(a) and 21(b), since the actual transmission speed of the network is larger than the value of R in terms of calculation, a large amount of data can be transmitted as compare with a case where the network actually provides transmission service at the speed of value R. Accordingly, the number of packet output operation(output queue selection) will be rapidly increased, with the result that the value of Fi will become larger rapidly in proportion to the increase of the packet output operation. That is, if the actual transmission speed of the network keeps higher than the value R in terms of calculation, the value Fi, or the scheduled output time will be rapidly increased as compared with actual time passage.
If the actual transmission speed of the network keeps higher than the value R in terms of calculation, the above-described rapid increase of Fi will continue. Thus, overflow is caused due to the bit number restriction regarding the value of Fi. If overflow is caused in the value of Fi of a certain queue block, this value of Fi is handled as an extremely small value as compared with the value of Fi of other queue block.
If the scheduled output time Fi is deviated from the real time as described above, the following error will be caused. That is, in the packet scheduler 102, since the value Fi of the certain queue block in which overflow is caused is handled as an extremely small value as compared with the value Fi of other queue block, this certain queue block is continuously selected as a queue block having a packet to be outputted with a priority.
For this reason, other queues are unreasonably restricted in assignment of a bandwidth utilized for packet transmission, with the result that it becomes impossible to guarantee the bandwidth reservation for all of the queues. Further, since the comparison of the value of scheduled output time, Fi cannot be effected in a fair manner, bandwidth resources cannot be assigned to queues in a fair manner. In this way, although it is an original intention for the WFQ algorithm to ensure bandwidth reservation and bandwidth assignment in a fair manner, the packet transferring apparatus fails to ensure bandwidth reservation and bandwidth assignment in a fair manner.